/**
 * 
 */
package merisis.traitspace.impl;

import static java.lang.String.format;
import static org.apache.solr.util.OpenBitSet.intersectionCount;

import java.util.HashMap;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.Logger;

import merisis.traitspace.History;
import merisis.util.BitUtil;

import org.apache.solr.util.OpenBitSet;

class SketchImpl {

	private final static Logger logger;
	static {
		logger = Logger.getLogger(SketchImpl.class.getName());
	}

	private OpenBitSet backgroud = new OpenBitSet();

	private OpenBitSet source = new OpenBitSet();

	private OpenBitSet tspectrum;

	private OpenBitSet focus;

	private History history;

	private Map<Long, OpenBitSet> footprintsMap = new HashMap<Long, OpenBitSet>();

	public SketchImpl(History history) {

		this.history = history;
	}

	public void setBackground(OpenBitSet bg) {

		this.backgroud = bg;
	}

	public void setSource(OpenBitSet bound) {

		this.source = bound;
	}

	public void setPart(OpenBitSet part) {

		this.focus = part;
	}

	public HistoricalHierarchyImpl historical() {

		// if (isDirty) {
		//
		// search();
		// }
		//
		// return new HistoricalHierarchyImpl(footprintsMap, sliced);

		throw new UnsupportedOperationException();
	}

	public OpenBitSet focus() {

		OpenBitSet part = focus;

		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("background: {");
			BitUtil.format(sb, backgroud, ",");
			sb.append("}, source: {");
			BitUtil.format(sb, source, ",");
			sb.append("}, guide: {");
			BitUtil.format(sb, part, ",");
			sb.append("}");
			logger.finest(sb.toString());
		}

		OpenBitSet bound = new OpenBitSet();
		if (backgroud != null)
			bound.or(backgroud);

		if (source != null)
			bound.or(source);

		if (bound.isEmpty())
			return null;

		focus = null;
		OpenBitSet sliced = null;

		OpenBitSet queue = new OpenBitSet();
		queue.or(bound);

		boolean sdetermined = false;
		OpenBitSet supremum = new OpenBitSet();
		long numOfBoundPoints = bound.cardinality();
		if (numOfBoundPoints == 1) {

			supremum.set(bound.nextSetBit(0));
			sdetermined = true;
		}

		OpenBitSet involved = new OpenBitSet();
		while (true) {

			long node = queue.nextSetBit(0);
			if (node < 0)
				break;

			queue.clear(node);
			involved.set(node);

			OpenBitSet nodeFootprints = footprintsMap.get(node);
			if (nodeFootprints == null) {
				nodeFootprints = new OpenBitSet();
				nodeFootprints.set(node);
				footprintsMap.put(node, nodeFootprints);
			}

			if (!sdetermined) {

				while (true) {

					if (intersectionCount(supremum, nodeFootprints) > 0)
						break;

					if (intersectionCount(bound, nodeFootprints) != numOfBoundPoints)
						break;

					for (long s = supremum.nextSetBit(0); s >= 0; s = supremum
							.nextSetBit(s + 1)) {
						OpenBitSet footprints = footprintsMap.get(s);
						if (footprints.get(node)) {
							supremum.clear(s);
						}
					}

					supremum.set(node);
					break;
				}
			}

			if (part != null && part.get(node))
				continue;

			long[] nextpoints = history.next(node);
			if (nextpoints == null) {
				continue;
			}

			for (int j = 0; j < nextpoints.length; j++) {

				long point = nextpoints[j];

				OpenBitSet footprints = footprintsMap.get(point);
				if (footprints == null) {
					footprints = new OpenBitSet();
					footprintsMap.put(point, footprints);
				}

				footprints.set(point);
				footprints.or(nodeFootprints);

				queue.set(point);
			}
		}

		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("involved: {");
			BitUtil.format(sb, involved, ",");
			sb.append("}, supremum: {");
			BitUtil.format(sb, supremum, ",");
			sb.append("}");
			logger.finest(sb.toString());
		}

		if (supremum.isEmpty())
			return null;

		long infimum = -1;
		if (part != null && !part.isEmpty()) {

			while (true) {

				long p1 = part.nextSetBit(0);
				if (p1 < 0)
					break;

				OpenBitSet fp = footprintsMap.get(p1);
				if (fp == null)
					break;
				if (intersectionCount(fp, supremum) == 0)
					break;

				long p2 = part.nextSetBit(p1 + 1);
				if (p2 < 0) {
					infimum = p1;
					break;
				}

				OpenBitSet bs = new OpenBitSet();
				bs.or(fp);
				for (p2 = part.nextSetBit(p1 + 1); p2 >= 0; p2 = part
						.nextSetBit(p2 + 1)) {

					fp = footprintsMap.get(p2);
					bs.and(fp);
					if (fp.isEmpty())
						break;
				}

				for (long pt = bs.nextSetBit(0); pt >= 0; pt = bs
						.nextSetBit(pt + 1)) {

					fp = footprintsMap.get(pt);

					bs.andNot(fp);
					bs.set(pt);
				}

				infimum = bs.nextSetBit(0);
				break;
			}
		}

		if (logger.isLoggable(Level.FINEST)) {
			logger.finest("infimum: " + infimum);
		}

		if (part != null && !part.isEmpty() && infimum < 0) {
			sliced = null;
			logger.finest("no infimum");
			return null;
		}

		sliced = new OpenBitSet();
		if (part == null || part.isEmpty()) {
			sliced.or(involved);
		} else {
			OpenBitSet fp = footprintsMap.get(infimum);
			if (fp != null)
				sliced.or(fp);
		}

		for (long node = sliced.nextSetBit(0); node >= 0; node = sliced
				.nextSetBit(node + 1)) {

			OpenBitSet fp = footprintsMap.get(node);
			if (fp == null)
				continue;

			if (intersectionCount(fp, supremum) == 0)
				sliced.clear(node);
		}

		if (part != null) {
			for (long node = part.nextSetBit(0); node >= 0; node = part
					.nextSetBit(node + 1)) {

				if (supremum.get(node))
					continue;

				sliced.clear(node);
			}
		}

		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("siliced: ");
			BitUtil.format(sb, sliced, ",");
			logger.finest(sb.toString());
		}

		// if (logger.isLoggable(Level.FINEST)) {
		// StringBuilder sb = new StringBuilder();
		//
		// // logger.finest(dumpStateDetail(sb).toString());
		// }

		HistoricalHierarchyImpl hhi;
		hhi = new HistoricalHierarchyImpl(footprintsMap, sliced);
		this.focus = hhi.rollHistory(0);
		// OpenBitSet minimum = new OpenBitSet();
		// minimumOfTraits(minimum, sliced);
		// this.focused = minimum;
		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("focus: ");
			BitUtil.format(sb, focus, ",");
			logger.finest(sb.toString());
		}

		return focus;
	}
	
	public void setFocus(OpenBitSet objective) {
		
		this.focus = objective;

		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("set focus: {");
			BitUtil.format(sb, focus, ",");
			sb.append("}");
			logger.finest(sb.toString());
		}
	}

	public OpenBitSet tspectrum(OpenBitSet tprism) {

		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("background: {");
			BitUtil.format(sb, backgroud, ",");
			sb.append("}, source: {");
			BitUtil.format(sb, source, ",");
			sb.append("}, guide: {");
			BitUtil.format(sb, tprism, ",");
			sb.append("}");
			logger.finest(sb.toString());
		}

		if (focus == null)
			return null;

		OpenBitSet bound = new OpenBitSet();
		if (source != null)
			bound.or(source);
		if (backgroud != null)
			bound.or(backgroud);

		traverse(tprism);

		OpenBitSet selected = new OpenBitSet();

		long numOfTraits = tprism.cardinality();

		OpenBitSet queue = new OpenBitSet();
		queue.or(focus);
		OpenBitSet involved = new OpenBitSet();
		while (true) {

			long node = queue.nextSetBit(0);
			if (node < 0)
				break;

			queue.clear(node);
			involved.set(node);

			OpenBitSet nodeFootprints = footprintsMap.get(node);
			if (nodeFootprints == null)
				continue;

			if (intersectionCount(bound, nodeFootprints) == 0
					|| intersectionCount(tprism, nodeFootprints) == 0) {

				continue;
			}

			long[] preivios = history.previous(node);
			if (preivios == null)
				continue;

			boolean nosup = false;

			for (int j = 0; j < preivios.length; j++) {

				long point = preivios[j];

				OpenBitSet footprints = footprintsMap.get(point);
				if (footprints == null)
					continue;

				if (intersectionCount(bound, footprints) == 0)
					continue;

				if (intersectionCount(tprism, footprints) == numOfTraits) {

					queue.set(point);
					nosup = true;
				}
			}

			if (!nosup) {
				selected.set(node);
			}
		}

		tspectrum = selected;

		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("on traits {");
			BitUtil.format(sb, tprism, ",");
			sb.append("}, t-spectrum: {");
			BitUtil.format(sb, tspectrum, ",");
			sb.append("}");
			logger.finest(sb.toString());
		}

		return tspectrum;
	}
	
	public OpenBitSet complement(OpenBitSet traits) {
		
		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("background: {");
			BitUtil.format(sb, backgroud, ",");
			sb.append("}, source: {");
			BitUtil.format(sb, source, ",");
			sb.append("}, focus: {");
			BitUtil.format(sb, focus, ",");
			sb.append("}, the complement of {");
			BitUtil.format(sb, traits, ",");
			sb.append("}");
			logger.finest(sb.toString());
		}
		
		if (traits == null)
			return null;
		
		traverse(traits);

		if (focus == null || focus.isEmpty())
			return null;

		// negative spectrum
		OpenBitSet nselected = new OpenBitSet();
		for (long node = focus.nextSetBit(0); node >= 0; node = focus
				.nextSetBit(node + 1)) {

			long[] preivios = history.previous(node);
			if (preivios == null)
				continue;

			for (int j = 0; j < preivios.length; j++) {

				long point = preivios[j];
				
				
				if (backgroud.get(point))
					continue;

				if (traits.get(point))
					continue;
				
				OpenBitSet footprints = footprintsMap.get(point);
				if (footprints == null) {
					OpenBitSet s = new OpenBitSet();
					s.set(point);
					traverse(s);
					nselected.set(point);
					continue;
				}
				
				if (source != null && intersectionCount(source, footprints) == 0)
					continue;
				
				if (traits != null && intersectionCount(traits, footprints) > 0) {
					continue;
				}

				nselected.set(point);
			}
		}

		OpenBitSet complement = new OpenBitSet();
		minimumOfTraits(complement, nselected);

		if (logger.isLoggable(Level.FINEST)) {
			StringBuilder sb = new StringBuilder();
			sb.append("complement: {");
			BitUtil.format(sb, complement, ",");
			sb.append("}");
			logger.finest(sb.toString());
		}

		return complement;
	}
	
	private void traverse(OpenBitSet s) {

		OpenBitSet queue = new OpenBitSet();
		queue.or(s);

		// traverse the traits
		OpenBitSet involved = new OpenBitSet();
		while (true) {

			long node = queue.nextSetBit(0);
			if (node < 0)
				break;

			queue.clear(node);
			involved.set(node);

			OpenBitSet nodeFootprints = footprintsMap.get(node);
			if (nodeFootprints == null) {
				nodeFootprints = new OpenBitSet();
				nodeFootprints.set(node);
				footprintsMap.put(node, nodeFootprints);
			}

			long[] nextpoints = history.next(node);
			if (nextpoints == null)
				continue;

			for (int j = 0; j < nextpoints.length; j++) {

				long point = nextpoints[j];

				OpenBitSet footprints = footprintsMap.get(point);
				if (footprints == null) {
					footprints = new OpenBitSet();
					footprintsMap.put(point, footprints);
				}

				footprints.set(point);
				footprints.or(nodeFootprints);

				queue.set(point);
			}
		}

//		 if (logger.isLoggable(Level.FINEST)) {
//		 StringBuilder sb = new StringBuilder();
//		 logger.finest(dumpStateDetail(sb).toString());
//		 }
	}

	private void minimumOfTraits(OpenBitSet minimum, OpenBitSet nselected) {

		if (nselected == null || nselected.isEmpty())
			return;

		long p = nselected.nextSetBit(0);
		minimum.set(p);
		for (p = nselected.nextSetBit(p + 1); p >= 0; p = nselected
				.nextSetBit(p + 1)) {

			OpenBitSet fp1 = footprintsMap.get(p);
			if (OpenBitSet.andNotCount(fp1, minimum) > 0) {
				minimum.andNot(fp1);
				minimum.set(p);
			}
		}
	}

	private StringBuilder dumpStateDetail(StringBuilder sb) {

		sb.append("== Footprints: \n");
		OpenBitSet points = new OpenBitSet();
		for (long p : footprintsMap.keySet()) {
			points.set(p);
		}

		for (long j = points.nextSetBit(0); j >= 0; j = points
				.nextSetBit(j + 1)) {

			sb.append(format("%4d", j));
			sb.append("/{");
			OpenBitSet fp = footprintsMap.get(j);
			BitUtil.format(sb, fp, ",");
			sb.append('}');
			sb.append(' ');
			sb.append('\n');
		}

		return sb;
	}
}